/*
 * Copyright (C) 2011 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package android.util;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 *一个缓存，它拥有对有限数量值的强引用。 每次访问一个值时，它都会被移到队列头部。
 * 将值添加到完整缓存时，该队列末尾的值将被逐出，并可能有资格进行垃圾回收。
 *
 * 如果您的缓存值包含需要明确释放的资源，请重写 {@link #entryRemoved}.
 *
 * 如果需要为相应的键计算缓存，就算没有对应的缓存，请覆盖{@link #create}。
 * 这简化了调用代码，允许它假定一个值总是会被​​返回，即使有一个缓存未命中。
 *
 *默认情况下，高速缓存大小是根据条目数衡量的。
 * 覆盖{@link #sizeOf}以按不同单位调整缓存大小。 例如，此缓存限制为4MiB of bitmaps:
 *
 * int cacheSize = 4 * 1024 * 1024; // 4MiB
 *   LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {
 *       protected int sizeOf(String key, Bitmap value) {
 *           return value.getByteCount();
 *       }
 *这个类是线程安全的。 通过在缓存上同步来自动执行多个缓存操作
 *   synchronized (cache) {
 *     if (cache.get(key) == null) {
 *         cache.put(key, value);
 *     }
 *   }}
 *
 * 该类不允许将null用作键或值。
 * 从{@link #get}，{@link #put}或{@link #remove}返回的null值是明确的：密钥不在缓存中
 *
 */
public class LruCache<K, V> {
    private final LinkedHashMap<K, V> map;

    /** 此缓存的单位大小。 不一定是元素的数量。 */
    private int size;
    private int maxSize;

    //调用{@link #put}的次数
    private int putCount;
    //{@link #create（Object）}返回值的次数。
    private int createCount;
    //已被驱逐的值的数量
    private int evictionCount;
    //已经存在的次数
    private int hitCount;
    private int missCount;

    /**
     * @param maxSize 对于不覆盖{@link #sizeOf}的缓存，这是缓存中的最大条目数。
     *               对于所有其他缓存，这是此缓存中条目大小的最大总和。
     *
     */
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }

    /**
     * Sets the size of the cache.
     * @param maxSize The new maximum size.
     *
     * @hide
     */
    public void resize(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }

        synchronized (this) {
            this.maxSize = maxSize;
        }
        //修改大小
        trimToSize(maxSize);
    }

    /**
     * 如果它存在于缓存中或可以由{@code #create}创建，则返回{@code key}的值。
     * 如果返回值，则将其移至队列头部。 如果值没有被缓存并且不能被创建，则返回null。
     *
     */
    public final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V mapValue;
        synchronized (this) {
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

        /*
        试创建一个值。 这可能需要很长时间，并且create（）返回时地图可能会有所不同。
        如果在create（）正在工作时将冲突值添加到地图，则我们将该值保留在地图中并释放创建的值。
         */

        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }

        synchronized (this) {
            createCount++;
            mapValue = map.put(key, createdValue);

            if (mapValue != null) {
                // 有一个冲突，以至于最后放弃
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue);
            }
        }

        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            trimToSize(maxSize);
            return createdValue;
        }
    }

    /**
     * 缓存{@code key}的{code}值。 该值被移动到队列的头部。
     *
     * @return 之前的值由{@code key}映射
     */
    public final V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }

        V previous;
        synchronized (this) {
            putCount++;
            size += safeSizeOf(key, value);
            previous = map.put(key, value);
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }

        trimToSize(maxSize);
        return previous;
    }

    /**
     * @param maxSize 返回之前缓存的最大大小。 可能是-1来驱逐甚至0大小的元素。
     */
    private void trimToSize(int maxSize) {
        while (true) {
            K key;
            V value;
            synchronized (this) {
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }

                if (size <= maxSize) {
                    break;
                }

                // BEGIN LAYOUTLIB CHANGE
                // 获取链表中的最后一项。
                // 这样做效率不高，这里的目标是最大限度地减少与平台版本相比的变化
                Map.Entry<K, V> toEvict = null;
                for (Map.Entry<K, V> entry : map.entrySet()) {
                    toEvict = entry;
                }
                // END LAYOUTLIB CHANGE

                if (toEvict == null) {
                    break;
                }

                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }

            entryRemoved(true, key, value, null);
        }
    }

    /**
     * 删除{@code key}条目（如果存在）。
     *
     * @return 之前的值由{@code key}映射。
     */
    public final V remove(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V previous;
        synchronized (this) {
            previous = map.remove(key);
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            entryRemoved(false, key, previous, null);
        }

        return previous;
    }

    /**
     * 被驱逐或删除的条目调用。
     * 当某个值被驱逐以腾出空间时，通过调用{@link #remove}或@link #put}的调用来取代此方法。
     * 默认实现什么都不做。
     * .
     *该方法在没有同步的情况下被调用：其他线程可以在该方法执行时访问缓存。
     *
     * @param evicted 如果要删除条目以腾出空间，则为true;如果删除是由{@link #put}或{@link #remove}引起的，则为false。
     * @param newValue ：{@code key}的新值，如果存在的话。 如果非null，则此删除是由{@link #put}引起的。
     *                 否则，它是由驱逐或{@link #remove}造成的。
     */
    protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

    /**
     * 在缓存未命中后调用以计算相应键的值。 返回计算值，如果不能计算值，则返回null。 默认实现返回null。
     *
     * <p>该方法在没有同步的情况下被调用：其他线程可以在该方法执行时访问缓存。
     *
     *
     * 如果此方法返回时缓存中存在{@code key}的值，则创建的值将与{@link #entryRemoved}一起释放并丢弃。
     * 当多个线程同时请求同一个键（导致创建多个值）时，
     * 或者当另一个线程调用{@link #put}而另一个线程正在为同一个键创建值时，会发生这种情况。
     *
     */
    protected V create(K key) {
        return null;
    }

    private int safeSizeOf(K key, V value) {
        int result = sizeOf(key, value);
        if (result < 0) {
            throw new IllegalStateException("Negative size: " + key + "=" + value);
        }
        return result;
    }

    /**
     * 以用户定义的单位返回{@code key}和{code code}的条目大小。
     * 默认实现返回1，此时：size是条目数量， max size是条目的最大数量。
     *
     *条目的大小在缓存中时不能更改。
     */
    protected int sizeOf(K key, V value) {
        return 1;
    }

    /**
     * 清除缓存，在每个删除的条目上调用{@link #entryRemoved}。
     */
    public final void evictAll() {
        trimToSize(-1); // -1 will evict 0-sized elements
    }

    /**
     * 对于不覆盖{@link #sizeOf}的缓存，这将返回缓存中的条目数。
     * 对于所有其他缓存，这将返回此缓存中条目的大小总和。
     */
    public synchronized final int size() {
        return size;
    }

    /**
     * 对于不覆盖{@link #sizeOf}的缓存，这将返回缓存中的最大条目数。
     * 对于所有其他缓存，这将返回此缓存中条目大小的最大总和。
     */
    public synchronized final int maxSize() {
        return maxSize;
    }

    /**
     * 返回{@link #get}返回缓存中已存在的值的次数
     */
    public synchronized final int hitCount() {
        return hitCount;
    }

    /**
     * Returns the number of times {@link #get} returned null or required a new
     * value to be created.
     */
    public synchronized final int missCount() {
        return missCount;
    }

    /**
     * 返回{@link #create（Object）}返回值的次数。
     */
    public synchronized final int createCount() {
        return createCount;
    }

    /**
     *返回调用{@link #put}的次数
     */
    public synchronized final int putCount() {
        return putCount;
    }

    /**
     * 返回已被驱逐的值的数量
     */
    public synchronized final int evictionCount() {
        return evictionCount;
    }

    /**
     * 返回缓存中当前内容的副本，从最近最少访问到最近访问的顺序排列。
     */
    public synchronized final Map<K, V> snapshot() {
        return new LinkedHashMap<K, V>(map);
    }

    @Override public synchronized final String toString() {
        int accesses = hitCount + missCount;
        int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0;
        return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]",
                maxSize, hitCount, missCount, hitPercent);
    }
}
